package org.example.Greedy_Algorithm;

import java.util.ArrayList;
import java.util.Arrays;

public class Maximum_subarray_and {
    public static void main(String[] args) {
        //最大子数组和

        //给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
        //子数组 是数组中的一个连续部分。
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        int i = maxSubArray(nums);
        System.out.println(i);
    }

    public static int maxSubArray(int[] nums) {
        int result = Integer.MIN_VALUE;
        int value = 0;
        for (int i = 0; i < nums.length; i++) {
            value+=nums[i];
            if (result<value){
                result = value;
            }
            if (value<=0) value = 0;
        }
        return result;
    }
    //超时了，还是太菜了,但是思路是对的
    public static int maxSubArray2(int[] nums) {
        int curr = 0;
        ArrayList<Integer> list = new ArrayList<>();
        while (curr < nums.length && nums[curr] <= 0) {
            curr++;
        }
        if (curr == nums.length) {
            Arrays.sort(nums);
            return nums[nums.length - 1];
        }
        int value = 0;
        int i = curr;
        while (i < nums.length) {
            if (value + nums[i] > value) {
                value = value + nums[i];
                i++;
            } else if ((value + nums[i]) < value && (value + nums[i]) > 0) {
                list.add(value);
                value = value + nums[i];
                i++;
            } else if ((value + nums[i]) < value && (value + nums[i]) <= 0) {
                list.add(value);
                while (i < nums.length && nums[i] <= 0) {
                    i++;
                }
                if (i < nums.length) {
                    value = nums[i];
                    i++;
                };

            }
        }
        for (Integer integer : list) {
            if (value < integer) value = integer;
        }
        return value;
    }
}
